//Tuesday, December 15 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <math.h>
#include <sstream>
#include <algorithm>

using namespace std;

class StrongPrimePower
{
public:
	vector <int> baseAndExponent(string n)
	{
		vector<int> ret;
		long long N;
		stringstream s(n);
		s >> N;
// 		cout << N << endl;
		for(int q=2; q<60; q++)
		{
			double pp = pow(N, 1.0/q);
			int p = (int) round(pp);
 			cout << p << ", " << q << endl;
			if(isprime(p) == false) continue;
			long long product = 1;
			for(int i=0; i<q; i++)
				product *= p;
// 			long long product = (long long)pow(1.0*p, 1.0*q);
			if(product == N)
			{
				ret.push_back(p);
				ret.push_back(q);
				break;
			}
		}
		return ret;
	}
	bool isprime(int n)
	{
		for(int i=2; i*i<=n; i++)
			if(n % i == 0)
				return false;
		return true;
	}
};
